Massively parallel computers each including tens of thousands of connected processors draw attention in the high-performance computing (HPC) field. A massively parallel computer including tens of thousands of nodes is designed so that a hardware cost per node is constant regardless of the scale of the system. In an internode connection network of nodes, a direct network is typically used to interconnect one node to another. The hardware cost of the direct network is determined by the number of ports on each node, and remains constant regardless of the scale of the system. One of the multidimensional mesh and the multidimensional torus is typically used as a connection topology of the direct network in a massively parallel computer formed of tens of thousands of nodes.
In such a system, deadlock in which a communication interruption is caused by a request to transfer circularly a plurality of packets has to be avoided. As a technique to avoid such a deadlock, the dimension order routing is known. The dimension-order routing determines the dimension order of communication lines. A routing technique is disclosed (William J. Dally, Charles L. Seitz, “Deadlock-Free Message Routing in Multiprocessor Interconnection Networks,” IEEE TRANSACTIONS ON COMPUTERS Vol. C-36, May 1987). In accordance with the disclosed routing technique, dual virtual channels having a high value and a low value as channel numbers are allocated to each node, and the channel numbers of transfer destinations are arranged in an ascending order or a descending order.
If a system having a scale of tens of thousands of nodes is shut down for maintenance each time any node malfunctions, the uptime of the system is reduced. Fault robustness is important on such a system. Even if some of the nodes are at fault, the system with the fault robustness preferably maintains communications with the other nodes used. However, the communication line is fixed beforehand in the dimension order routing, and if one node is at fault, the communication performed via that node becomes difficult.